package personal_exercise;

import javafx.util.Pair;
import model.ListNode;
import model.TreeNode;

import java.util.*;

public class Demo4 {

    // LCR 170. 交易逆序对的总数
    private int res;
    public int reversePairs(int[] record) {
        mergeSort(record, 0, record.length - 1);
        return res;
    }
    private void mergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);

        // 升序排序
        int cur1 = left, cur2 = mid + 1, k = 0;
        int[] tmp = new int[right - left + 1];
        while (cur1 <= mid && cur2 <= right) {
            if (nums[cur1] > nums[cur2]) {
                res += mid - cur1 + 1;
                tmp[k++] = nums[cur2++];
            } else {
                tmp[k++] = nums[cur1++];
            }
        }
        while (cur1 <= mid) tmp[k++] = nums[cur1++];;
        while (cur2 <= right) tmp[k++] = nums[cur2++];

        // 填回原数组
        for (k = 0; left <= right; k++, left++) {
            nums[left] = tmp[k];
        }
    }



    // 174. 地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        // 1. 创建 dp 表
        // 2. 初始化 : 从最下面一行和最右边一列开始初始化
        // 3. 填表
        // 4. 返回值
        // dp[i][j]: 以 (i, j) 为起点,到达终点所需的最低健康点数
        int n = dungeon.length, m = dungeon[0].length;
        int[][] dp = new int[n + 1][m + 1];
        for (int i = n; i >= 0; i--) {
            dp[i][m] = Integer.MAX_VALUE;
        }
        for (int j = m; j >= 0; j--) {
            dp[n][j] = Integer.MAX_VALUE;
        }
        dp[n][m - 1] = dp[n - 1][m] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int j = m - 1; j >= 0; j--) {
                dp[i][j] = Math.max(1, Math.min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j]);
            }
        }
        return dp[0][0];
    }



    // 315. 计算右侧小于当前元素的个数
//    private int[] indexs;       // 存储原始数组元素的下标
//    private int[] tmpArray;     // 归并排序过程中开辟的临时空间
//    private int[] countsArray;  // 结果数组
//
//    public List<Integer> countSmaller(int[] nums) {
//        int n = nums.length;
//        tmpArray = new int[n];
//        countsArray = new int[n];
//        Arrays.fill(countsArray, 0);
//        indexs = new int[n];
//        for (int i = 0; i < n; i++) indexs[i] = i;
//        // 对数组进行降序归并排序(按下标)
//        mergeSort(nums, 0, n - 1);
//        List<Integer> res = new ArrayList<>();
//        for (int x : countsArray) res.add(x);
//        return res;
//    }
//    private void mergeSort(int[] nums, int left, int right) {
//        if (left >= right) return;
//
//        // 1. 将数组进行左右分区
//        int mid = (left + right) / 2;
//        mergeSort(nums, left, mid);
//        mergeSort(nums, mid + 1, right);
//
//        // 2.降序排序:处理一左一右的情况,并合并数组
//        int cur1 = left, cur2 = mid + 1, k = left;
//        while (cur1 <= mid && cur2 <= right) {
//            // indexs[cur]: 原始数组元素所在的下标
//            if (nums[indexs[cur1]] > nums[indexs[cur2]]) {
//                countsArray[indexs[cur1]] += right - cur2 + 1;
//                tmpArray[k++] = indexs[cur1++];
//            } else {
//                tmpArray[k++] = indexs[cur2++];
//            }
//        }
//        while (cur1 <= mid) tmpArray[k++] = indexs[cur1++];;
//        while (cur2 <= right) tmpArray[k++] = indexs[cur2++];
//
//        // 填回原数组
//        while (left <= right) {
//            indexs[left] = tmpArray[left++];
//        }
//    }



    // 477. 汉明距离总和
    public int totalHammingDistance(int[] nums) {
        int res = 0, n = nums.length;
        //  0 <= nums[i] <= 1e9  ==> 符号位都为0
        for (int i = 0; i < 31; i++) {
            int count = 0; // 统计当前比特位为 1 的元素个数
            for (int x : nums) {
                count += (x>>i) & 1;
            }
            res += count * (n - count);
        }
        return res;
    }



    // 1026. 节点与其祖先之间的最大差值
//    private int res = 0;
    public int maxAncestorDiff(TreeNode root) {
        // 要使 V = |A.val - B.val| 最大, 则 A和B 的距离应越大
        dfs(root, root.val, root.val);
        return res;
    }
    private void dfs(TreeNode root, int ancestryMaxValue, int ancestryMinValue) {
        if (root == null) return;
        res = Math.max(res, Math.max(Math.abs(root.val - ancestryMaxValue), Math.abs(root.val - ancestryMinValue)));

        if (root.val > ancestryMaxValue) ancestryMaxValue = root.val;
        if (root.val < ancestryMinValue) ancestryMinValue = root.val;
        dfs(root.left, ancestryMaxValue, ancestryMinValue);
        dfs(root.right, ancestryMaxValue, ancestryMinValue);
    }



    // 980. 不同路径 III
//    private int res;
    private int n, m;
    private int sum;    // 统计空方格的个数
    private int count;  // 统计到达终点时走过的空方格的个数
    private boolean[][] vis;    // 记录方格是否走过
    public int uniquePathsIII(int[][] grid) {
        n = grid.length;
        m = grid[0].length;
        vis = new boolean[n][m];
        int startX = -1, startY = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) sum++;
                else if (grid[i][j] == 1) {
                    startX = i;
                    startY = j;
                }
            }
        }

        dfs(grid, startX, startY);
        return res;
    }
    private int[] dx = {0,0,1,-1};
    private int[] dy = {1,-1,0,0};
    private void dfs(int[][] arr, int i, int j) {
        if (arr[i][j] == 2) {
            if (count == sum) res++;
            return;
        }
        if (arr[i][j] == 0) count++;
        vis[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < n && y >= 0 && y < m && arr[x][y] != -1 && !vis[x][y]) {
                dfs(arr, x, y);
            }
        }
        if (arr[i][j] == 0) count--;
        vis[i][j] = false;
    }



    // 502. IPO
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Integer[] indexs = new Integer[n];
        for (int i = 0; i < n; i++) indexs[i] = i;
        // 以下标的方式将启动资本按从小到大的方式排序
        Arrays.sort(indexs, (a, b) -> capital[a] - capital[b]);

        // 将能够达到启动资本的项目加入优先级队列
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> profits[b] - profits[a]);
        int i = 0;
        while (i < n && w >= capital[indexs[i]]) maxHeap.add(indexs[i++]);
        while (k > 0 && !maxHeap.isEmpty()) {
            k--;
            w += profits[maxHeap.poll()];
            while (i < n && w >= capital[indexs[i]]) maxHeap.add(indexs[i++]);
        }
        return w;
    }



    // 662. 二叉树最大宽度
    public int widthOfBinaryTree(TreeNode root) {
        List<Pair<TreeNode, Integer>> list = new ArrayList<>();
        // 对每个结点以完全二叉树的形式编号,根结点为 1
        list.add(new Pair(root, 1));

        int ret = 1;
        while (true) {
            List<Pair<TreeNode, Integer>> tmp = new ArrayList<>();
            // 对下一层不为 null 的结点加入列表
            for (Pair<TreeNode,Integer> pair : list) {
                TreeNode node = pair.getKey();
                int num = pair.getValue();
                if (node.left != null) {
                    tmp.add(new Pair(node.left, num * 2));
                }
                if (node.right != null) {
                    tmp.add(new Pair(node.right, num * 2 + 1));
                }
            }
            // 最大宽度可能为每层最后一个结点的编号 - 第一个结点的编号 + 1
            int sz = list.size();
            ret = Math.max(ret, list.get(sz - 1).getValue() - list.get(0).getValue() + 1);
            if (tmp.isEmpty()) break;
            list = tmp;
        }
        return ret;
    }




    // 1926. 迷宫中离入口最近的出口
    public int nearestExit(char[][] maze, int[] entrance) {
        int row = maze.length, col = maze[0].length;
        boolean[][] vis = new boolean[row][col];
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{entrance[0], entrance[1]});
        vis[entrance[0]][entrance[1]] = true;

        int step = 0;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < row && y >= 0 && y < col && maze[x][y] == '.' && !vis[x][y]) {
                        if (x == 0 || x == row - 1 || y == 0 || y == col - 1) return step + 1;
                        q.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
            step++;
        }
        return -1;
    }



    // 91. 解码方法
    public int numDecodings(String s) {
        // dp[i]: 以 i 位置为结尾的子串有多少种解码方式
        int n = s.length();
        char[] arr = s.toCharArray();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = arr[0] != '0' ? 1 : 0;

        for (int i = 2; i <= n; i++) {
            char ch = arr[i - 1];
            if (ch != '0') dp[i] += dp[i - 1];
            char c = arr[i - 2];
            int num = (c - '0') * 10 + ch - '0';
            if (num >= 10 && num <= 26) {
                dp[i] += dp[i - 2];
            }
            if (dp[i] == 0) return 0;
        }
        return dp[n];
    }




    // 2671. 频率跟踪器
    class FrequencyTracker {
        private int[] num;      // 下标表示数字,值表示出现次数
        private int[] fre;      // 下标表示出现次数,值表示该出现频率的元素个数

        public FrequencyTracker() {
            num = new int[(int)1e5 + 1];
            fre = new int[(int)1e5 + 1];
        }

        public void add(int number) {
            int count = num[number];
            if (count > 0) {
                fre[count]--;
            }
            count = ++num[number];
            fre[count]++;
        }

        public void deleteOne(int number) {
            if (num[number] > 0) {
                fre[num[number]]--;
                if (--num[number] > 0) {
                    fre[num[number]]++;
                }
            }
        }

        public boolean hasFrequency(int frequency) {
            return fre[frequency] > 0;
        }
    }



    // 2641. 二叉树的堂兄弟节点 II
    public TreeNode replaceValueInTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        // 统计该层所有节点值的和
        int sum = root.val;
        while (!q.isEmpty()) {
            // 统计下一层所有节点的和
            int nextSum = 0;
            for (int sz = q.size(); sz-- > 0; ) {
                TreeNode node = q.poll();
                node.val = sum - node.val;
                if (node.left == null && node.right == null) continue;

                if (node.left != null && node.right != null) {
                    // 将该节点的两个子节点的值修改为两节点的和,即可使用 sum - node.val 计算结果
                    node.left.val = node.right.val = node.left.val + node.right.val;
                    nextSum += node.left.val;
                    q.offer(node.left);
                    q.offer(node.right);
                } else if (node.left != null) {
                    q.offer(node.left);
                    nextSum += node.left.val;
                } else {
                    q.offer(node.right);
                    nextSum += node.right.val;
                }
            }
            sum = nextSum;
        }
        return root;
    }




    // JZ13 机器人的运动范围
    public int movingCount(int threshold, int rows, int cols) {
        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{0,0});
        boolean[][] vis = new boolean[rows][cols];
        vis[0][0] = true;
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};

        int res = 1;
        while (!q.isEmpty()) {
            for (int sz = q.size(); sz-- > 0; ) {
                int[] arr = q.poll();
                int i = arr[0], j = arr[1];
                for (int k = 0; k < 4; k++) {
                    int x = i + dx[k], y = j + dy[k];
                    if (x >= 0 && x < rows && y >= 0 && y < cols && !vis[x][y]) {
                        int sum = 0;
                        for (int num = x; num > 0; num /= 10) sum += num % 10;
                        for (int num = y; num > 0; num /= 10) sum += num % 10;
                        if (sum > threshold) continue;
                        res++;
                        q.offer(new int[]{x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return res;
    }




    // JZ76 删除链表中重复的结点
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode newHead = new ListNode(-1);
        newHead.next = pHead;
        ListNode prev = newHead;

        for (ListNode cur = pHead; cur != null; ) {
            while (cur != null && cur.next != null && cur.next.val == cur.val) {
                ListNode tmp = cur.next;
                while (tmp != null && tmp.val == cur.val) {
                    tmp = tmp.next;
                }
                cur = tmp;
            }
            prev.next = cur;
            prev = cur;
            if (cur != null) cur = cur.next;
        }
        return newHead.next;
    }



    // JZ16 数值的整数次方
    public double Power(double base, int exponent) {
        if (base == 0) return 0;
        if (exponent == 0) return 1;
        double ret = myPow(base, exponent);
        return exponent > 0 ? ret : 1.0 / ret;
    }
    private double myPow(double base, int exponent) {
        if (exponent == 0) return 1;
        double res = myPow(base, exponent / 2);
        return exponent % 2 == 0 ? res * res : res * res * base;
    }


    // JZ85 连续子数组的最大和(二)
    public int[] FindGreatestSumOfSubArray (int[] array) {
        int n = array.length;
        // dp[i][0]: 以 i 位置为结尾的所有子数组的最大和
        // dp[i][1]: 以 i 位置为结尾的所有子数组中和最大的子数组的长度
        int[][] dp = new int[n][2];
        dp[0][0] = array[0];
        dp[0][1] = 1;

        int index = 0, maxSum = array[0];
        for (int i = 1; i < n; i++) {
            dp[i][0] = array[i];
            dp[i][1] = 1;
            if (dp[i - 1][0] >= 0) {
                dp[i][0] += dp[i - 1][0];
                dp[i][1] += dp[i - 1][1];
            }

            if (dp[i][0] >= maxSum) {
                if (dp[i][0] > maxSum || dp[i][1] > dp[index][1]) {
                    index = i;
                    maxSum = dp[i][0];
                }
            }
        }
        return Arrays.copyOfRange(array, index - dp[index][1] + 1, index + 1);
    }



    // 437. 路径总和 III
    int ret;
    public int pathSum(TreeNode root, int targetSum) {
        if(root == null) return 0;
        dfs(root, (long)targetSum);
        pathSum(root.left, targetSum);
        pathSum(root.right, targetSum);
        return ret;
    }
    public void dfs(TreeNode root, long targetSum) {
        if(root == null) return;
        targetSum -= root.val;
        if(targetSum == 0) {
            ret++;
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
    }



    // JZ33 二叉搜索树的后序遍历序列
    private int pos;
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0) return false;
        return checkTreeOrder(sequence, 0, sequence.length - 1);
    }
    private boolean checkTreeOrder(int[] sequence, int left, int right) {
        if (left >= right) return true;
        // 找到第一个比当前树根结点大的值
        int rootVal = sequence[right], cur = left;
        while (cur < right && sequence[cur] < rootVal) cur++;
        // 当前位置后的所有元素都应该比 rootVal 大
        for (int i = cur; i < right; i++) {
            if (sequence[i] < rootVal) return false;
        }
        return checkTreeOrder(sequence, left, cur - 1) && checkTreeOrder(sequence, cur, right - 1);
    }



    // JZ26 树的子结构
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        // 先序遍历,若root.val == root2.val,判断是否为子结构
        if (root1 == null || root2 == null) return false;
        if (root1.val == root2.val) {
            if (check(root1, root2)) return true;
        }
        if (HasSubtree(root1.left, root2)) return true;
        return HasSubtree(root1.right, root2);
    }
    // 判断是否为其子结构
    private boolean check(TreeNode root1, TreeNode root2) {
        if (root1 == null || root1.val != root2.val) return false;
        if (root2.left != null && !check(root1.left, root2.left)) return false;
        if (root2.right != null && !check(root1.right, root2.right)) return false;
        return true;
    }



    // JZ64 求1+2+3+...+n
    public int Sum_Solution(int n) {
        try {
            int num = 1 / n;
            return Sum_Solution(n - 1) + n;
        } catch(Exception e) {
            return 0;
        }
    }


    // JZ66 构建乘积数组
    public int[] multiply (int[] A) {
        int n = A.length;
        // 前缀积f[i]: 前 i - 1个数的乘积
        int[] f = new int[n];
        f[0] = 1;
        for (int i = 1; i < n; i++) {
            f[i] = f[i - 1] * A[i - 1];
        }

        int[] res = new int[n];
        int product = 1;
        for (int i = n - 1; i >= 0; i--) {
            res[i] = f[i] * product;
            product *= A[i];
        }
        return res;
    }



    // 371. 两整数之和
    public int getSum(int a, int b) {
        while(b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }



    // 503. 下一个更大元素 II
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        final int INF = (int)1e9 + 1;
        Arrays.fill(res, INF);

        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0, count = 0; count < 2 * n; i = (i + 1) % n, count++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                int index = stack.peek();
                if (res[index] == INF) {
                    res[index] = nums[i];
                }
                stack.pop();
            }
            stack.push(i);
        }

        // 此时栈中剩下元素均找不到下一个更大的元素
        while (!stack.isEmpty()) {
            int index = stack.pop();
            if (res[index] == INF) res[index] = -1;
        }
        return res;
    }



}
